{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "01fa0ad7-8625-4a34-8e30-fdaad4df5840",
   "metadata": {},
   "source": [
    "# 排序算法"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "76072310-ba12-4e1f-93b4-1963b2051366",
   "metadata": {},
   "source": [
    "## 最\"像人\"的排序算法---选择排序\n",
    "设想一个场景,如果是想要为自己最喜欢的食物排一个表,你会怎么做?\n",
    "1. 先将自己最喜欢的食物选择出来\n",
    "2. 放到表的第一位\n",
    "3. 再找第二喜欢的食物\n",
    "4. 放到表中的下一位\n",
    "5. ....以此类推...直到最后一个食物\n",
    "6. 那么这张表就是排序之后的喜爱食物表(当然你可以排其他东西)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d4b6d564-e0ad-479b-8be5-cefd7f3a5ffb",
   "metadata": {},
   "source": [
    "### 我们将任务改变成对数字排序,现在给出一个列表"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "f2bf7952-b08b-42b9-a8b2-057c48b8a1f6",
   "metadata": {},
   "outputs": [],
   "source": [
    "old_list = [3,1,2,5,4] #排序前列表\n",
    "new_list = []    #排序后的新列表\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e6296fea-c7ef-4681-b59c-45e1c250531d",
   "metadata": {},
   "source": [
    "### 先将最大或是最小的数字拿出来放到新表中,我们可以将任务分解为两个部分\n",
    "1. 找出最大或最小值\n",
    "2. 将数字放入新数组\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7ef55ff3-268e-4652-91fe-49c2159ca92f",
   "metadata": {},
   "source": [
    "#### <font color = \"red\">任务1:</font>找出最大或最小值,我们以降序(从大到小)举例\n",
    "实现逻辑:\n",
    "1. 先定义一个变量去当作最大值\n",
    "2. 遍历整个列表,有比最大值大的就将这个值作为最大值\n",
    "3. 最后将最大值的索引下标返回"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "e9e6cf8e-16fc-405f-866e-4b091b2259ad",
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_max_index(arr):\n",
    "    #定义一个最大值,先将第一个值作为最大值,遍历过程中再去修改\n",
    "    max_index = 0\n",
    "    max_num = arr[max_index]\n",
    "    for i in range(len(arr)):\n",
    "        #如果这个值大于最大值,那就暂定它是最大值\n",
    "        if arr[i]>max_num:\n",
    "            #修改最大索引\n",
    "            max_index = i\n",
    "            #修改最大值\n",
    "            max_num = arr[i]\n",
    "\n",
    "    return max_index\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "0658dd88-9d15-471f-a35c-6e9d1b2a3eb9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#测试一下\n",
    "find_max_index(old_list)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9d4975ff-1d1e-431a-bce6-1e4a3b9c252e",
   "metadata": {},
   "source": [
    "#### <font color = \"red\">任务2:</font>将这个最大值放到新的列表中\n",
    "实现逻辑:\n",
    "1. 执行函数获取最大索引\n",
    "2. 将旧列表的下标位的值删除\n",
    "   > 我们每一次函数执行都是找最大值\n",
    "   >\n",
    "   > 如果执行后这个最大值不删除,接下来每一次找的值都是这个最大值,无法找出第二大的值\n",
    "   > \n",
    "   > 最大值删除后,再去找最大值得到的就是第二大的值了\n",
    "3. 将这个值放入新列表"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "f4e1e35e-d116-4c38-9c2e-73f3ed108d55",
   "metadata": {},
   "outputs": [],
   "source": [
    "#找出最大值,并且将值删除\n",
    "max_num = old_list.pop(find_max_index(old_list))\n",
    "\n",
    "#放入新列表\n",
    "new_list.append(max_num)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "363378c7-9713-4d83-a866-9d76b1e9650c",
   "metadata": {},
   "source": [
    "#### 我们多次执行上面的逻辑\n",
    "每执行一次都可以找到当前的最大值\n",
    "\n",
    "> 第一次找最大的,然后删除掉最大的\n",
    "> \n",
    "> 此时列表中剩下的最大的值就是第二大的\n",
    "> \n",
    "> 以此类推,于是我们执行**列表长度次**即可全部排序找出\n",
    ">\n",
    "于是我们得出完整代码"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "381ef71e-5e6b-4169-823a-303c4f1db1bb",
   "metadata": {},
   "outputs": [],
   "source": [
    "def choose_sort(arr):\n",
    "\n",
    "    new_list = []\n",
    "    \n",
    "    for i in range(len(arr)):\n",
    "        #找出最大值,并且将值删除\n",
    "        max_num = arr.pop(find_max_index(arr))\n",
    "        \n",
    "        #放入新列表\n",
    "        new_list.append(max_num)\n",
    "\n",
    "    return new_list\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "d72329e3-acfb-4f5e-96e1-20b19fc6abff",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[9, 6, 5, 4, 4, 3, 2, 2, 1, 1]"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 测试一下\n",
    "test = [9,1,2,3,4,6,5,1,2,4]\n",
    "choose_sort(test)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3510c7bc-14d8-4307-8757-372b712c1ed3",
   "metadata": {},
   "source": [
    "## 思考一下:这种写法有什么问题?\n",
    "\n",
    "> 需要多余创建一个新列表,而且删除一个数字,其实计算机背地里要做很多事情\n",
    "+ 占内存-----增加空间复杂度\n",
    "+ 多操作-----增加时间复杂度\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "922c5dce-c153-4dcc-9874-01e0a0a59282",
   "metadata": {},
   "source": [
    "我们换一种思路,如果我找到了最大值,直接放在当前列表的最前面就好了\n",
    "比如\n",
    "```python\n",
    "3 1 2 5 4 # 找到最大的5,索引是3\n",
    "    |          # 放到最前面,原本的3不能丢,于是3放在原来5的位置\n",
    "    |          # 也就是 两个值交换位置\n",
    "5 1 2 3 4 #此时前面的0位置是有序的,后面是无序的\n",
    "    |     #再次找到最大值就应该放到1的位置\n",
    "    |     #找到1下标-4下标的最大值是4 ,索引为4,再次交换    \n",
    "5 4 2 3 1\n",
    "    |     \n",
    "   ... #重复,直到最后一位,发现只剩一个值,不需要再选择了,只剩它了\n",
    "    |\n",
    "5 4 3 2 1 #于是结束\n",
    "    \n",
    "```\n",
    "### 得出结论\n",
    "+ 每次找到最大值与前面的值进行交换\n",
    "+ 从0找到n-1\n",
    "\n",
    "修改函数为"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "5b57c2a0-e5dd-4775-b39e-d0e2f07eb66c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def choose_sort(arr):\n",
    "    \n",
    "    for i in range(len(arr)-1):\n",
    "\n",
    "        #用i表示正在有序的下标\n",
    "\n",
    "        max_index = i\n",
    "        #找出最大值索引\n",
    "        for j in range(i+1,len(arr)):\n",
    "            if arr[max_index] < arr[j]:\n",
    "                max_index = j\n",
    "        \n",
    "        #交换\n",
    "        arr[i],arr[max_index] = arr[max_index],arr[i]\n",
    "\n",
    "        #直接操作原来列表,可以不用返回\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "c9caa629-0d83-4d12-8936-197eda446c63",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[8, 4, 3, 2, 1, 1]"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 测试一下\n",
    "test1 = [4,3,1,2,8,1]\n",
    "\n",
    "choose_sort(test1)\n",
    "\n",
    "test1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a6fb5851-266e-4a1e-a439-85798e9664f0",
   "metadata": {},
   "source": [
    "## 本节要求\n",
    "\n",
    "1. 要理解什么是选择排序\n",
    "2. 可以画出每次排序后的数字序列\n",
    "3. 实现关键代码\n",
    "   + 交换的代码\n",
    "   + 查找最大索引代码\n",
    "   + 两个循环的范围\n",
    "\n",
    "拓展尝试:\n",
    "> 完整代码实现\n",
    ">\n",
    "> 将最终版本的查找最大值以函数的形式封装\n",
    ">\n",
    "> 想一想,有什么办法还有什么可以优化?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f2f58dd5-ee7c-4c65-b213-d2387a4b3875",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
